import java.util.HashMap;
import java.util.Map;

class LRUCache {

    // 缓存
    private Map<Integer, Integer> cache;
    // 用于标记，值越大越优先淘汰
    private Map<Integer, Integer> flag;
    // 最大容量
    private int MAX_CAPACITY;


    public LRUCache(int capacity) {
        MAX_CAPACITY = capacity;
        cache =  new HashMap<>(capacity);
        flag = new HashMap<>(capacity);
    }

    /**
     * 从缓存中获取值
     */
    public int get(int key) {
        if (cache.containsKey(key)){
            // 当前元素置0，其它元素值+1
            flag.put(key, 0);
            increment(key);
            return cache.get(key);
        }
        return -1;
    }

    /**
     * 除key以外的都自增
     */
    private void increment(int key) {
        for (Integer i : flag.keySet()) {
            if (i != key){
                flag.put(i, flag.get(i)+1);
            }
        }
    }

    /**
     * 往缓存中添加元素
     */
    public void put(int key, int value) {
        if (cache.size() < MAX_CAPACITY){
            // 缓存容量足够，直接添加，并将新加入元素标记值置为初值0
            cache.put(key, value);
            flag.put(key, 0);
            increment(key);
            return;
        }
        if (cache.containsKey(key)){
            // 缓存容量不够，但是当前添加的key已在缓存中存在，直接更新即可
            cache.put(key, value);
            flag.put(key, 0);
            increment(key);
            return;
        }
        // 缓存容量不够且key不在缓存中，使用 LRU 策略淘汰缓存中的数据
        int i = getDieOutKey();
        cache.remove(i);
        cache.put(key, value);
        flag.put(key, 0);
        increment(key);
    }

    /**
     * 获取淘汰元素的索引
     */
    private int getDieOutKey() {
        int max = Integer.MIN_VALUE;
        int key = 0;
        for (Integer i : flag.keySet()) {
            if (flag.get(i)>max){
                max = flag.get(i);
                key = i;
            }
        }
        flag.remove(key);
        return key;
    }
}